1. Field of the Invention
The present invention generally relates to a data retrieving apparatus and a data retrieving method. Particularly, the present invention relates to a controlling method, a controlling program, and a control data structure which are provided with a function for retrieving data matching under a specified retrieval rule at a high rate from a database which is a group of fixed length data whose bit length is constant. More specifically, the present invention relates to a communication controlling method; a method, a computer readable media and a data structure for controlling communication that realize a high rate retrieval for a destination route in an inter-network relaying apparatus; and a high rate retrieval executed under a plurality of retrieval rules for a filtering function.
2. Description of the Related Art
In a variety of fields there is the need for realizing a retrieval of desired fixed length data at a high rate from a database. Particularly, in the database used in the inter-network relaying apparatus for determination of relay destination and determination of relay processing, a growing demand exists for, to name a few, retrieval destination addresses using a special retrieval rule, retrieval using a plurality of different retrieval rules, and high rate retrieval.
When retrieving a desired IP (Internet Protocol) address from a route database used for an inter-network relaying apparatus (router, etc.), it is necessary to retrieve the IP address based on the LPM (Longest Prefix Match) rule. The IP address basically comprises a network address and a host address. The length of the network address is indicated as a prefix. The length of the prefix is variable, and by aggregating the IP addresses, the route database is composed. The aggregation is to cause one prefix to be representative for a plurality of the prefixes that have identical higher-order bits. The representative prefix is expressed by the common higher-order bits. As a result, when retrieving the route database including the aggregated IP addresses, it is induced that a plurality of the IP addresses match. The LPM rule is a method in which the IP address that is the longest in a plurality of the matching IP addresses is a matching result. The TCAM (Ternary Content Addressable Memory) is a representative example of a conventional technique for realizing high rate retrieval based on the LPM rule. However, the memory size of a TCAM is not as large as that of a DRAM (Dynamic Random Access Memory). Thus, many TCAMs are necessary to accommodate the route database including a large number of the IP addresses by utilizing the TCAMs. Thus, a large-sized database can not be composed because of the limitations of the power supply and packages. This is a problem.
It is also well known to use a table which is retrieved by a plurality of the retrieval rules and composed with the fixed length data for a router and the like. A table using the ACL (Access Control List) including a filtering function for determining whether or not to transfer is a typical example for using the plurality of the retrieval rules. In one example using the ACL, the ACL is composed with the fixed length data comprising user data and seven elements, including a TOS (Type of Service) of eight bits, a source IP address (32 bits), a destination IP address (32 bits), a protocol (eight bits), a source port (16 bits), a destination port (16 bits), and a control flag of eight bits. The user data is data which becomes a retrieval result when the retrieval result is the match. The fixed length data of the ACL is retrieved by a comparison matching rule (different from the LPM) by a prefix mask for the source IP address and the destination IP address, by a numerical value comparison rule for the source port and the destination port, and by the comparison matching rule for other data; in addition, each fixed length data of the ACL includes a priority order. When the comparison result of all the elements matches, it is acknowledged that the fixed length data matches. If a plurality of the fixed length data match, the fixed length data whose priority order is the highest becomes the retrieval result. In a comparison by the comparison matching rule with the prefix mask, a match determination is executed by comparing each bit by using the prefix mask stored in association with the source IP address and the destination IP address which are parts of the fixed length data of the ACL. In a comparison by the numerical value comparing rule, an unsigned numerical value comparison is executed between the maximum value and the minimum value of the source port and the destination port configured in the fixed length data of the ACL table, and if the port to be compared exists between the maximum value and the minimum value, it is acknowledged that the comparison result is the match. Finally, in a comparison by the comparison matching rule, if all of the TOS, the protocol, and the control flag configured in the fixed length data of the ACL table match with a comparison value, it is acknowledged that the comparison result is the match.
Only the TCAM is included in the conventional technique for retrieving the ACL table in a high rate. In addition, the numerical value comparison can not be executed for the TCAM. Thus, a part which needs the numerical value comparison is divided into a plurality of parts, and a requested functionality is achieved by match-comparing each of the divided parts. Thus, as a result, one fixed length data of the ACL table is divided to a plurality of (a few to a few dozen) pieces of the fixed length data, and is stored in the ACL table. As described above, the retrieval for comparing in a high rate by a plurality of the retrieval rules depends on the TCAM, so that the same problem as the above in the TCAM is also induced.
The inventor of the present invention has already filed a patent application: Japanese Patent Application No. 2006-512434 (International Patent Application No. PCT/JP2004/04641) [Patent Document 1].
[Patent Document 1] Japanese Patent Application No. 2006-512434 (International Patent Application No. PCT/JP2004/04641)